package com.computer.fundamentals.algorithm;

/**
 * 经典问题——木头切割
 *  -----------------------------------------------------------------------------------------------------------------
 *  给定长度为n的数组，每个元素代表一个木头的长度，木头可以任意截断，从这堆木头中截出至少k个相同长度为m的木块。已知k，求max(m)。
 *  输入两行，第一行n, k，第二行为数组序列。输出最大值。
 *
 *  示例：
 *      输入
 *          5 5
 *          4 7 2 10 5
 *      输出
 *          4
 *  -----------------------------------------------------------------------------------------------------------------
 */
public class WoodCuttingProblem {

    /**
     * 解决方案
     *  方案一：暴力求解
     *      ① 假设一个初始化的m=1
     *      ② 线性扫描整个数组，对每一块木头尝试切分为m大小的木块，并计算切分的总和
     *      ③ 如果超过k，那么此时m有效，m++继续重头遍历
     *      时间复杂度：O(N * Max(nums[i]))
     *      空间复杂度：O(1)
     *
     *  方案二：二分查找
     *      对于方案一, 不难发现m是线性探测并且是有序的, 因此可以采取二分来优化m的寻找过程
     *      m的左边界是1, 那么右边界呢？我们可以预先遍历数组, 求出最大木头长度, 由最大木头长度作为有边界
     */
    public static int solution(int[] woods, int k) {
        int left = 0, right = 0;
        for (int wood: woods) {
            right = Math.max(right, wood);
        }
        int res = 0;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int count = woodCuttingCount(woods, mid);
            if (count < k) {
                right = mid - 1;
            }else {
                left = mid + 1;
                res = Math.max(res, mid);
            }
        }

        return res;
    }

    /**
     * 模拟切分，计算出长度为m的木块总数
     */
    public static int woodCuttingCount(int[] woods, int m) {
        int count = 0;
        for (int i = 0;i < woods.length;i++) {
            count += woods[i] / m;
        }
        return count;
    }

    /**
     * 测试
     */
    public static void main(String[] args) {

        System.out.println("------------测试------------");
        int res = solution(new int[] {4, 7, 100, 10, 5}, 5);
        System.out.println(res);

    }
}